package ordered_table

import (
	"sort"
)

func medianSlidingWindow(nums []int, k int) []float64 {
	bst := NewBSTree()
	for i:=0; i<k-1; i++ {
		bst.Add(nums[i])
	}
	ans := make([]float64, len(nums)-k+1)
	for i:=k-1; i<len(nums); i++{
		bst.Add(nums[i])
		if k % 2 == 0 {
			up := bst.GetIndexKey(k/2)
			down := bst.GetIndexKey(k/2+1)
			ans[i-k+1] = (up+down)/2
		} else {
			ans[i-k+1] = bst.GetIndexKey(k/2+1)
		}
		bst.Remove(nums[i-k+1])
	}
	return ans
}

func medianSlidingWindow2(nums []int, k int) []float64 {
	win := make([]int, k)
	for i:=0; i<k-1; i++ {
		win[i] = nums[i]
	}
	ans := make([]float64, len(nums)-k+1)
	index := 0
	for i:=k-1; i<len(nums); i++{
		win[k-1] = nums[i]
		ans[index] = GetArrMedian(win)
		index++
		win = win[1:]
		win = append(win, 0)
	}
	return ans
}

func GetArrMedian(arr []int) float64 {
	cp := make([]int, len(arr))
	copy(cp, arr)
	sort.Slice(cp, func(i, j int) bool {
		return cp[i] < cp[j]
	})
	l := len(cp)
	if l % 2 == 0 {
		return (float64(cp[l/2-1]) + float64(cp[l/2]))/2
	} else {
		return float64(cp[l/2])
	}
}